package leetcode.hard;

/**
 * ClassName: $42_Trap
 * Description:
 * date: 2022-02-15 15:25
 *
 * @author liyifan
 */
public class $42_Trap {
    public int trap(int[] height) {
        int len = height.length;
        int[] max_left = new int[len];
        int[] max_right = new int[len];
        for(int i = 1;i < len;i++){
            max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
        }
        for (int i = len - 2;i >= 0;i--){
            max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
        }
        int ans = 0;
        for (int i = 0;i < len;i++) {
            int min = Math.min(max_left[i], max_right[i]);
            if (height[i] < min) {
                ans += (min - height[i]);
            }
        }
        return ans;
    }
}
